package algorithms.dijkstra;

import java.awt.Point;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Vector;

import pathfinding.gui.Map;
import algorithms.DescriptedPoint;
import algorithms.PathFindingAlgorithm;
import algorithms.SearchResult;

/**
 * Class to calculate paths in two dimensional array
 * using Dijkstra's algorithm. Not guaranteed to implement
 * the algorithm correctly.
 * 
 * See more about Dijkstra's algorithm: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
 * 
 * @author arttu viljakainen
 *
 */
public class DijkstraStyleAlgorithm implements PathFindingAlgorithm{
	
	private SearchResult searchResult;
	private int[][] arrayMap;
	private Vector<DNode> allNodes;
	private DNode startNode;
	private DNode goalNode;
	private long searchTime;
	private Deque<DescriptedPoint> finalPath;
	private Deque<DescriptedPoint> finalUsedCells;
	
	/**
	 * Finds the path and returns SearchResult.
	 */
	@Override
	public SearchResult findPath(Point start, Point goal, Map map) {
		if(start == null || goal == null || map == null)
			return new SearchResult();
		
		searchResult = new SearchResult();
		arrayMap = mapToArray(map);
		allNodes = createAllNodesAndSetPathEndpoints(arrayMap, start, goal);
		
		startNode.setDistanceFromStart(0);
		
		long timeBeforeSearch = System.nanoTime();
		
		PriorityQueue<DNode> usedCells = calculateDistancesFrom(startNode, goalNode);
		PriorityQueue<DNode> path = calculateFinalPath(startNode, goalNode);
		
		searchTime = System.nanoTime() - timeBeforeSearch;
		long searchTimeInMillis = searchTime / 1000000;
		
		finalPath = new ArrayDeque<DescriptedPoint>();
		finalUsedCells = new ArrayDeque<DescriptedPoint>();
		int pathLength = path.size();
		while(! path.isEmpty()) {
			DNode node = path.remove();
			DescriptedPoint point = new DescriptedPoint(node.getLocation().x, node.getLocation().y);
			point.setDescription(
					"<html>" +
					"Path cell <br> " +
					"Distance from start " + (node.getDistanceFromStart() / 10) + "<br>" + 
					"Path cells " + (pathLength - 2) + "<br>" + 
					"Steps " + (pathLength - 1) + "<br>" +
					"Search time " + searchTimeInMillis + " ms " +
					"</html>");
			finalPath.add(point);
		}
		while(! usedCells.isEmpty()) {
			DNode node = usedCells.remove();
			DescriptedPoint point = new DescriptedPoint(node.getLocation().x, node.getLocation().y);
			point.setDescription("<html>" +
					"Visited cell <br> " +
					"Distance from start " + (node.getDistanceFromStart() / 10) + 
					"</html>");
			finalUsedCells.add(point);
		}
		
		searchResult.setPath(finalPath);
		searchResult.setUsedCandidates(finalUsedCells);
		searchResult.setTimeInNanoseconds(searchTime);
		
		return searchResult;
	}
	
	/**
	 * Translates a Map to two dimensional array.
	 * 
	 * @param map
	 * @return
	 */
	private int[][] mapToArray(Map map) {
		int[][] arrayMap = new int[map.getRows()][map.getColumns()];
		
		for(int rowIndex = 0; rowIndex < map.getRows(); rowIndex ++) {
			for(int columnIndex = 0; columnIndex < map.getColumns(); columnIndex ++) {
				if(map.getMapCell(rowIndex, columnIndex).isWalkable())
					arrayMap[rowIndex][columnIndex] = 0;
				else
					arrayMap[rowIndex][columnIndex] = 1;
			}
		}
		
		return arrayMap;
	}
	
	/**
	 * Creates DNodes from two dimensional array and set start and end points.
	 * 
	 * @param arrayMap
	 * @param startPoint
	 * @param goalPoint
	 * @return All created nodes
	 */
	private Vector<DNode> createAllNodesAndSetPathEndpoints(int[][] arrayMap, Point startPoint, Point goalPoint) {
		Vector<DNode> allNodes = new Vector<DNode>();

		for(int rowIndex = 0; rowIndex < arrayMap.length; rowIndex ++) {
			for(int columnIndex = 0; columnIndex < arrayMap[0].length; columnIndex ++) {
				DNode node = new DNode(rowIndex, columnIndex, arrayMap[rowIndex][columnIndex]);
				allNodes.add(node);
				if(rowIndex == startPoint.y && columnIndex == startPoint.x) 
					startNode = node;
				if(rowIndex == goalPoint.y && columnIndex == goalPoint.x)
					goalNode = node;
			}
		}
		
		for(DNode node : allNodes) {
			node.addNodeNeighbours(arrayMap, allNodes);
		}
		
		return allNodes;
	}
		
	/**
	 * Returns the neighbour with shortes path to the start.
	 * 
	 * @param node
	 * @return Node with shortest path to the start
	 */
	private DNode getBestNeighbourOf(DNode node) {
		DNode best = null;
		for(DNode dn : node.getNeighbours()) {
			if(best == null || dn.getDistanceFromStart() < best.getDistanceFromStart()) {
				best = dn;
			}
		}
		
		return best;
	}
		
	/**
	 * Calculates distances from the start for all nodes until finds the goal.
	 * Returns all visited cells.
	 * 
	 * @param startNode
	 * @param goalNode
	 * @return Visited cells.
	 */
	private PriorityQueue<DNode> calculateDistancesFrom(DNode startNode, DNode goalNode) {
		PriorityQueue<DNode> nodes = new PriorityQueue<DNode>();
		LinkedList<DNode> stack = new LinkedList<DNode>();
		stack.add(startNode);
		nodes.add(startNode);
		
		while(! stack.isEmpty()) {
			DNode master = stack.poll();
						
			for(DNode node : master.getNeighbours()) {
				if(node.getDistanceFromStart() > (master.getDistanceFromStart() + distanceBetweenNeighbours(master.getLocation(), node.getLocation()))) {
					node.setDistanceFromStart(master.getDistanceFromStart() + distanceBetweenNeighbours(master.getLocation(), node.getLocation()));
				}
				if(! nodes.contains(node)) {
					stack.add(node);
					nodes.add(node);
				}
			}
			if(nodes.contains(goalNode))
				return nodes;
		}
		return nodes;
	}
	
	/**
	 * Returns the distance between neighbours.
	 * 
	 * @param node1
	 * @param node2
	 * @return distance
	 */
	private int distanceBetweenNeighbours(Point node1, Point node2) {
		if(node1.x == node2.x || node1.y == node2.y)
			return 10;
		else 
			return 11;
	}
		
	/**
	 * Calculates the final path using valuated nodes.
	 * 
	 * @param start
	 * @param goal
	 * @return Final path
	 */
	private PriorityQueue<DNode> calculateFinalPath(DNode start, DNode goal) {
		PriorityQueue<DNode> path = new PriorityQueue<DNode>();
		if(goal.getDistanceFromStart() == Integer.MAX_VALUE)
			return path;
		DNode next = goal;
		
		while(! next.equals(start)) {
			path.add(next);
			next = getBestNeighbourOf(next);
		}
		
		path.add(next);
		
		return path;
	}
		
	@Override
	public String toString() {
		return "Dijkstra-style";
	}

}
